package RecursiveSearcher;

/**
 * @ClassName LC21
 * @Description 合并两个有序链表
 * @Author ZJX
 * @Date 2024/9/11 16:41
 * @Version 1.0
 */

//   https://leetcode.cn/problems/merge-two-sorted-lists/

   class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

//  dfs 重复的子问题 找出头节点
// 出口 cur == null
public class LC21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        return dfs(list1, list2);
    }

    private ListNode dfs(ListNode cur1, ListNode cur2) {
        // 递归基准：当其中一个链表为空时，返回另一个链表
        if (cur1 == null) return cur2;
        if (cur2 == null) return cur1;

        // 选择较小的节点作为合并链表的当前节点
        if (cur1.val < cur2.val) {
            cur1.next = dfs(cur1.next, cur2); // 继续递归合并剩余部分
            return cur1;  // 返回当前较小节点
        } else {
            cur2.next = dfs(cur1, cur2.next); // 继续递归合并剩余部分
            return cur2;  // 返回当前较小节点
        }
    }

    // 创建链表的辅助函数
    private static ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode list1 = createLinkedList(new int[]{1, 3, 5});
        ListNode list2 = createLinkedList(new int[]{2, 4, 6});

        LC21 solution = new LC21();
        ListNode mergedList = solution.mergeTwoLists(list1, list2);
    }
}
